//Cracking the coding interview (5th), 2_5
//You have two numbers represented by a linked list, where each node contains a single digit.
//The digits are stored in reverse order, such that the 1's digit is at the head of the list.
//Write a function that adds the two numbers and returns the sum as a linked list.
//EXAMPLE
//Input: (7->1->6)+(5->9->2). That is 617 + 295.
//Output:2->1->9. That is, 912.
//FOLLOW UP
//Suppose the digits are stored in forward order. Repeat the above problem.
//EXAMPLE
//Input: (6->1->7)+(2->9->5). That is, 617+295.
//Output:9->1->2. That is, 912.
//
//Author: Fan Yang and Hao Cui
//Time: 5:16pm-

#include<stdio.h>
#include<stdlib.h>
#include <string.h>

struct Number
{
	int d;
	struct Number * next;
};

void NewNode(struct Number * head, int v)
{
	struct Number * t=head;
	while(t->next!=NULL)
	{
		t=t->next;
	}
	struct Number * p=(struct Number *)malloc(sizeof(struct Number));
	p->d=v;
	p->next=NULL;
	t->next=p;
}

void Add(struct Number * N1, struct Number * N2, struct Number * N3)
{
	struct Number * p1=N1,* p2=N2,* p3=N3;
	int c=0,flag1=0,flag2=0;
	while(1)
	{
		int t=0;
		if(p1!=NULL)
		{
			t+=p1->d;
			p1=p1->next;
		}
		else
			flag1=1;
		if(p2!=NULL)
		{
			t+=p2->d;
			p2=p2->next;
		}
		else 
			flag2=1;
		if(flag1&&flag2)
			break;
		p3->d=(t+c)%10;
		c=(t+c)/10;
		NewNode(N3,0);
		p3=p3->next;
	}
	if(c)
	{
		p3->d=c;
	}
}

typedef struct _data {
    int data;
    struct _data * next;
} DATA;

DATA* add2 (DATA *pa, DATA *pb)
{
    DATA *head, *p, *pp, *p1, *p2;

    int M, N, L, tmp;

    M = N = 0;

    p = pa;
    while (NULL != p)
    {
        M++;
        p = p->next;
    }
    p = pb;
    while (NULL != p)
    {
        N++;
        p = p->next;
    }

    L = M > N ? M - N : N - M;
    p1 = M > N ? pa : pb;
    p2 = M > N ? pb : pa;

    p = p1;
    while (L > 0)
    {
        p = p->next;
        L--;
    }
    while (p)
    {
        p->data += p2->data;
        p = p->next;
        p2 = p2->next;
    }
    
    head = (DATA *) malloc (sizeof(DATA));
    head->data = 0;
    head->next = p1;
    
    p = p1;
    pp = head;
    
    while (p)
    {
        if (p->data > 9)
        {
            pp->data++;
            p->data %= 10;
            pp = pp->next;
            while (pp != p)
            {
                pp->data = 0;
                pp = pp->next;
            }
            p = p->next;
        }
        else if (p->data == 9)
        {
            p = p->next;
        }
        else
        {
            pp = p;
            p = p->next;
        }
    }
    if (head->data > 0)
    {
        tmp = head->data;
        head->data = p1->data;
        p1->data = tmp;
        head->next = p1->next;
        p1->next = head;
    }
    else
    {
        free (head);
    }
    return p1;
}

int main()
{
  // First half
  {
	struct Number * D1=(struct Number *)malloc(sizeof(struct Number));
	struct Number * D2=(struct Number *)malloc(sizeof(struct Number));
	struct Number * D3=(struct Number *)malloc(sizeof(struct Number));
	struct Number * p;
	D1->d=7;
	D1->next=NULL;
	NewNode(D1,1);
	NewNode(D1,6);
	D2->d=5;
	D2->next=NULL;
	NewNode(D2,9);
	NewNode(D2,2);
	D3->d=0;
	D3->next=NULL;
	Add(D1,D2,D3);
	p=D3;
	while(p!=NULL)
	{
		printf("%d",p->d);
		p=p->next;
	}
  }
  
  // Second half
  {
    DATA *pa, *pb, *p, *pp;

    pa = (DATA *) malloc (sizeof(DATA));
    pb = (DATA *) malloc (sizeof(DATA));

    p = pa;
    p->data = 9;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 9;
    p->next = (DATA *) malloc (sizeof(DATA));
    p = p->next;
    p->data = 9;
    p->next = NULL;

    p = pb;
    p->data = 1;
    p->next = NULL;

    p = add2 (pa, pb);
    while (p)
    {
        printf ("%d", p->data);
        p = p->next;
    }
    printf ("\n");

    pp = NULL;
    p = pa;
    while (p)
    {
        pp = p;
        p = p->next;
        free (pp);
    }

    pp = NULL;
    p = pb;
    while (p)
    {
        pp = p;
        p = p->next;
        free (pp);
    }
  }
}




